home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C++ / Applications / HyperCuber 2.0 / source / NCube.cp < prev    next >
Encoding:
Text File  |  1993-09-25  |  6.5 KB  |  230 lines  |  [TEXT/KAHL]
  1. //|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  2. //| This file contains a procedure which creates an n-dimensional cube
  3. //|____________________________________________________________________
  4.  
  5. #include <fstream.h>
  6.  
  7.  
  8. //================================ Prototypes ===============================\\
  9.  
  10. long FindPath(Boolean *has_visited, long start_vertex, long n, ofstream *ofs, Boolean write);
  11.  
  12.  
  13.  
  14. //|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  15. //| Procedure CreateNCube
  16. //|
  17. //| Purpose: this procedure creates an n-cube file for any n
  18. //|
  19. //| Parameters: n:        the dimension of the n-cube
  20. //|             filename: name of file for n-cube descriptions
  21. //|_______________________________________________________________
  22.  
  23. void CreateNCube(long n, char *filename)
  24. {
  25.  
  26.     ofstream ofs;
  27.  
  28.     ofs.open(filename);                                    //  Open the output file
  29.     
  30.     ofs << 1 << '\n';                                    //  Write version number
  31.     ofs << n << '\n';                                    //  Write dimension of n-cube
  32.     ofs << 0  << '\n' << 0 << '\n';                        //  Write reserved zeros
  33.     
  34.     long num_vertices = 1L << n;                        //  Computer number of vertices
  35.     
  36.     ofs << num_vertices << '\n';                        //  Write number of vertices
  37.     
  38.     long i;
  39.     for (i = 0; i < num_vertices; i++)                    //  Write the vertices' coordinates
  40.         {
  41.         ofs << '(';                                        //  Write the left parenthesis
  42.         
  43.         long j;
  44.         for (j = 0; j < n; j++)                            //  This loop slices up i (the current vertex number)
  45.                                                         //    bit by bit.  For each 1-bit in i, a 1 is
  46.                                                         //    written to the file; for each 0-bit, a
  47.                                                         //    -1 coordinate is written.
  48.             {                                        
  49.             if (i & (1 << j))
  50.                 ofs << 1;                                //  This bit is a 1; write a 1
  51.             else
  52.                 ofs << -1;                                //  This bit is a 0; write a 0
  53.             
  54.             if (j != n-1)
  55.                 ofs << ", ";                            //  Write comma between coordinates (but not
  56.                                                         //    after the last coordinate
  57.             }
  58.         
  59.         ofs << ')' << '\n';                                //  Write the right parenthesis
  60.         }
  61.     
  62.     ofs << 1 << '\n';                                    //  Write the number of colors
  63.     ofs << "65535, 65535, 65535\n";                        //  Write the color
  64.  
  65.     long size_of_array = num_vertices*n*sizeof(Boolean);
  66.     Boolean **has_visited_handle =
  67.             (Boolean **) NewHandle(size_of_array);        //  Allocate space for the array
  68.     Boolean **has_visited_handle_temp =
  69.             (Boolean **) NewHandle(size_of_array);        //  Allocate space for the temporary array
  70.     
  71.     HLock((Handle) has_visited_handle);                    //  Lock down and dereference the arrays
  72.     HLock((Handle) has_visited_handle_temp);    
  73.     Boolean *has_visited = *has_visited_handle;
  74.     Boolean *has_visited_temp = *has_visited_handle_temp;
  75.  
  76.     for (i = 0; i < size_of_array; i++)                    //  Clear the arrays
  77.         has_visited[i] = FALSE;
  78.     BlockMove(has_visited, has_visited_temp, size_of_array);
  79.  
  80.     //  PASS 1: in this pass we count the number of paths we need to draw this object
  81.  
  82.     long num_paths_found = 0;
  83.     for (i = 0; i < num_vertices; i++)                    //  This loops through the vertices in order
  84.         while (FindPath(has_visited, i, n,
  85.                                             &ofs, FALSE))
  86.             num_paths_found++;                            //  Keep making paths until there are no
  87.                                                         //    more to be found.  
  88.  
  89.     ofs << num_paths_found << '\n';                        //  Write the number of paths
  90.     
  91.     //  PASS 2: in this pass we actually write the paths to disk
  92.     
  93.     for (i = 0; i < size_of_array; i++)                    //  Clear the array
  94.         has_visited[i] = FALSE;
  95.  
  96.     for (i = 0; i < num_vertices; i++)                    //  This loops through the vertices in order
  97.         {
  98.         long path_length;
  99.         do
  100.             {
  101.             BlockMove(has_visited, has_visited_temp,
  102.                                         size_of_array);    //  Make a copy of the array
  103.             path_length =
  104.                     FindPath(has_visited_temp,
  105.                                     i, n, &ofs, FALSE);    //  Find the length of the path (using copy)
  106.             
  107.             if (path_length)
  108.                 {
  109.                 ofs << '\n';
  110.                 ofs << 2 << '\n';                        //  Make this a path
  111.                 ofs << 1 << '\n';                        //  Draw with color 1
  112.                 ofs << path_length << '\n';                //  Write the length of this path
  113.                 
  114.                 FindPath(has_visited, i, n, &ofs, TRUE);//  Find the path again, this time writing it
  115.                                                         //    to the file.
  116.                 }
  117.             }
  118.         while (path_length > 0);                    //  Keep finding paths until there are none left
  119.  
  120.         }
  121.  
  122.     ofs.close();                                        //  Close the file
  123.             
  124. }    //==== CreateNCube() ====\\
  125.  
  126.  
  127.  
  128. //|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  129. //| Procedure FindPath
  130. //|
  131. //| Purpose: this procedure finds a path along the edges of the
  132. //|          n-cube, and writes the path to file.
  133. //|
  134. //| Parameters: has_visited:  the array of Booleans, indicating which vertices are already
  135. //|                           connected together.
  136. //|             start_vertex: the vertex to find a path from
  137. //|             n:            the dimension of the n-cube
  138. //|             write:        TRUE if the path should be written to file
  139. //|             ofs:          the output file stream to write to
  140. //|             returns length of path if a path was found, 0 otherwise
  141. //|_______________________________________________________________________________________
  142.  
  143. long FindPath(Boolean *has_visited, long start_vertex, long n, ofstream *ofs, Boolean write)
  144. {
  145.  
  146.     long current_vertex = start_vertex;                //  Start path with start_vertex
  147.  
  148.     long num_vertices = 1 << n;                        //  Find the total number of vertices
  149.     
  150.     long path_length = 0;                            //  Start with no vertices in path
  151.     
  152.     do
  153.         {
  154.         
  155.         long i;
  156.         for (i = 0; i < n; i++)
  157.             {
  158.             long next_vertex = current_vertex ^ (1 << i);//  Find adjacent vertex number by flipping
  159.                                                         //    one bit of the start vertex
  160.     
  161.             long to_index = current_vertex * n + i;        //  Find index of segment to start vertex
  162.             long from_index = next_vertex * n + i;        //  Find index of segment from start vertex
  163.             
  164.             if (!has_visited[to_index])                    //  Check if there is already a segment
  165.                                                         //    between current and next_vertex
  166.                 {
  167.                 
  168.                 has_visited[to_index] = TRUE;            //  Mark that there is now a connection
  169.                 has_visited[from_index] = TRUE;            //    both ways
  170.                 
  171.                 if (write)
  172.                     (*ofs) << current_vertex + 1 << '\n';//  Write the vertex
  173.                 
  174.                 path_length++;                            //  Path is now one more vertex in length
  175.                 
  176.                 current_vertex = next_vertex;            //  Start looking for the next vertex
  177.     
  178.                 break;                                    //  Get out of the for loop
  179.                             
  180.                 }    // end if
  181.                 
  182.             }    // end for
  183.         
  184.         if (i == n)
  185.             {
  186.             if (path_length)
  187.                 {
  188.                 if (write)
  189.                     (*ofs) << current_vertex + 1 << '\n';//  Write the last vertex of a path
  190.                 path_length++;                            //  Count the last vertex in the length
  191.                 }
  192.             
  193.             break;                                        //  We didn't find another node; path done
  194.             }
  195.         
  196.         }
  197.     while (TRUE);
  198.  
  199.     return path_length;                                    //  Return the path length
  200.  
  201. }    //==== FindPath() ====\\
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.